import collections


class Solution:
    def minInsertions(self, s: str) -> int:
        size = len(s)

        # 定义状态矩阵
        dp = [[size] * size for _ in range(size)]
        dp[0][-1] = 0

        queue = collections.deque([(0, size - 1)])

        ans = size

        while queue:
            i, j = queue.popleft()
            if i == j:
                ans = min(ans, dp[i][j])
            elif i == j - 1:
                if s[i] == s[j]:
                    ans = min(ans, dp[i][j])
                else:
                    ans = min(ans, dp[i][j] + 1)
            else:
                if s[i] == s[j]:
                    if dp[i][j] < dp[i + 1][j - 1]:
                        dp[i + 1][j - 1] = dp[i][j]
                        queue.append((i + 1, j - 1))
                else:
                    if dp[i][j] + 1 < dp[i + 1][j]:
                        dp[i + 1][j] = dp[i][j] + 1
                        queue.append((i + 1, j))

                    if dp[i][j] + 1 < dp[i][j - 1]:
                        dp[i][j - 1] = dp[i][j] + 1
                        queue.append((i, j - 1))

        return ans


if __name__ == "__main__":
    print(Solution().minInsertions(s="zzazz"))  # 0
    print(Solution().minInsertions(s="mbadm"))  # 2
    print(Solution().minInsertions(s="leetcode"))  # 5
    print(Solution().minInsertions(s="g"))  # 0
    print(Solution().minInsertions(s="no"))  # 1
    print(Solution().minInsertions(s="tldjbqjdogipebqsohdypcxjqkrqltpgviqtqz"))  # 25
